/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    //使用一个快指针和一个慢指针
    //快指针每次走2步，慢指针每次走1步
    //如果有环，快慢指针相遇时，快指针套了慢指针k圈
    //假设head到环入口距离 a,入口到相遇位置距离b，相遇位置往后到入口距离c
    //则相遇时slow走了 a+b ,fast走了 a+b+k(b+c) 因为套圈了,而此时慢指针一定没有走完一圈
    // 为什么没走完一圈：假设slow到入口时，fast在slow后面一个，fast再套slow一圈时一定可以追上，此时fast走了一圈多，slow一定没走完一圈
    //有 2(a+b) = a+b + k(b+c) --> 2a + 2b = a + b + b + c + (k - 1)(b + c)
    //---> a - c = k(b + c)
    //也就是说，head从a这段距离在走完c步之后，剩下距离是圈长的整数倍；而slow走完c步就到入口了
    //后面head和slow继续走，会在入口相遇，此时就是入口

    let fast = head
    let slow = head
    while (fast && fast.next) { //快指针指向末尾或者末尾的下一个null
        fast = fast.next.next
        slow = slow.next
        if (slow === fast) { //第一次相遇，head开始走
            while (slow !== head) {
                slow = slow.next
                head = head.next
            }
            return slow
        }
    }
    //如果没有环
    return null
};